////#define _CRT_SECURE_NO_WANINGS 1
////#pragma warning(disable: 4996)
////#include <stdio.h>
////
////int main() {
////    int n = 0;
////    scanf("%d", &n);
////    int arr[10000];
////    for (int i = 0; i < n; i++)
////    {
////        scanf("%d", &arr[i]);
////    }
////    for (int i = 0; i < n; i++)
////    {
////        int a[2];
////        a[0] = 1; a[1] = 2;
////        int j = 0;
////        for (j = 2; j <= arr[i]; j++)
////        {
////            a[j] = 2 * a[j - 1] + a[j - 2];
////        }
////        if (arr[i] < j)
////            printf("%d\n", a[arr[i]]);
////        printf("%d\n", a[j]);
////    }
////
////    return 0;
////}
////
////#include <stdio.h>
////update verse
////int main() {
////    int n = 0;
////    scanf("%d", &n);
////    for (int i = 0; i < n; i++)
////    {
////        int k = 0;
////        scanf("%d", &k);
////        if (k < 3)
////        {
////            printf("%d\n", k);
////            continue;
////        }
////        int a1 = 1, a2 = 2, a3 = 0;
////        for (int j = 2; j < k; j++)
////        {
////            a3 = a2 * 2 + a1;
////            a1 = a2;
////            a2 = a3;
////        }
////        printf("%d\n", a3);
////    }
////    return 0;
////}
//#include <stdio.h>
//
//int main() {
//    int arr[1000000] = { 0 };
//    arr[0] = 1; arr[1] = 2;
//    for (int i = 2; i < 1000000; i++)
//    {
//        arr[i] = arr[i - 1] * 2 + arr[i - 2];
//        arr[i] %= 32767;
//    }
//    int n = 0;
//    scanf("%d", &n);
//    while (n--)
//    {
//        int k = 0;
//        scanf("%d", &k);
//        printf("%d\n", arr[k - 1]);
//    }
//    return 0;
//}